//3132. 找出与数组相加的整数 II
class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        //int ret=1000;
        //unordered_map<int,int> um;
        // for(int i=0;i<n;i++)
        // {
        //     cout<<nums1[i]<<' ';

        // }
        // cout<<endl;
        // for(int i=0;i<n-2;i++)
        // {
        //     cout<<nums2[i]<<' ';
            
        // }
        // cout<<endl;
        // int l=0,r=n-3,flag=3,ret=1000;
        // vector<int> s(3);
        // while(flag--)
        // {
            
        //     int s1=nums2[0]-nums1[l];
        //     s[l]=s1;
        //     int s2=nums2[n-3]-nums1[r];
        //     um[s1]++;
        //     um[s2]++;
        //     cout<<s1<<' '<<s2<<endl;
        //     if(s1==s2&&ret>s1)
        //         ret=s1;
        //     l++;
        //     r++;
        // }
        //cout<< ret<<endl;
        for(int i=2;i>=0;i--)//注意是从2到0遍历，保证找到的是最小的
        {
            int tem=nums2[0]-nums1[i];
            int l=i+1,r=1;
            while(l<n&&r<n-2&&l-r<=2)
            {
                if(nums2[r]-nums1[l]==tem)
                    r++;
                l++;
            }
            // if(r==n-2&&ret>tem)
            //     ret=tem;
            if(r==n-2)
                return tem;

        }
        // for(auto& e:um)
        // {
        //     cout<<e.first<<' '<<e.second<<endl;
        //     if(e.second>1&&ret>e.first)
        //     {
        //         ret=e.first;
        //     }
        // }
        
        // int ret=1000;
        
        return 0;
    }
};